package Tree;

//判断一个序列是否是二叉排序树的后序序列
public class IsFoundTreePost {
	public static void main(String[] args) {
		int[] a = { 1, 2, 3, 4, 5 };
		VerifySquenceOfBST(a);
	}

	public static boolean VerifySquenceOfBST(int[] sequence) {
		if (sequence.length <= 0) {
			return false;
		}
		// 长度小于等于2都是二叉树的
		// if(sequence.length<=2){
		// return true;
		// }
		int length = sequence.length;
		// 后序遍历最后一个值为根节点
		int i = 0;
		for (; i < length - 1; i++) {
			if (sequence[i] > sequence[length - 1])
				break;
		}
		// 对于右边的序列，若还有数据小于根结点的值，那么肯定不是二叉搜索树的后序
		for (int j = i + 1; j < length - 1; j++) {
			if (sequence[j] < sequence[length - 1])
				return false;
		}
		boolean leftIsVerift = true;
		if (i > 0) {
			int[] left = new int[i];
			for (int k = 0; k < i; k++) {
				left[k] = sequence[k];
			}
			leftIsVerift = VerifySquenceOfBST(left);
		}
		boolean rightIsVerift = true;
		if (i < length - 1) {
			int[] right = new int[length - 1 - i];
			for (int k = i; k < length - 1; k++) {
				right[k - i] = sequence[k];
			}
			rightIsVerift = VerifySquenceOfBST(right);
		}
		return leftIsVerift && rightIsVerift;
		/*
		 * if(sequence.length<0){ return false; } if(sequence.length<=2){ return
		 * true; } int length=sequence.length; //后序遍历最后一个值为根节点 int i=0;
		 * for(;i<length-1;i++){ if(sequence[i]>sequence[length-1]) break; }
		 * //对于右边的序列，若还有数据小于根结点的值，那么肯定不是二叉搜索树的后序 for(int j=i+1;j<length-1;j++){
		 * if(sequence[j]<sequence[length-1]) return false; } int[] left=new
		 * int[i]; for(int k=0;k<i;k++){ left[k]=sequence[k]; }
		 * System.out.println(length+"length"+i); int[] right=new
		 * int[length-1-i]; for(int k=i;k<length-1;k++){ right[k-i]=sequence[k];
		 * } return VerifySquenceOfBST(left)&&VerifySquenceOfBST(right);
		 */
	}
}
